# -*- coding: utf-8 -*-
"""
Created on Tue Sep 25 17:02:19 2018

@author: duxiaoqin
Functions:
    (1)MazeDraw class
"""
from Stack import Stack
from graphics import *
from maze import *
from myqueue import Queue


class MazeDraw:
    def __init__(self, win, maze):
        self.width = maze.numCols()
        self.height = maze.numRows()
        self.win = win
        self.win.setCoords(0.0, 0.0, self.width + 2, self.height + 2)

        self.rect_points = []
        for row in range(self.height):
            for col in range(self.width):
                point1 = Point(col + 1, self.height - row)
                point2 = Point(col + 1 + 1, self.height - row + 1)
                if maze[row, col] == Maze.EMPTY:
                    color = 'green'
                else:
                    color = 'blue'
                self.rect_points.append((point1, point2, color))
        self.rectangles = []
        for p1, p2, color in self.rect_points:
            rect = Rectangle(p1, p2)
            rect.setFill(color)
            self.rectangles.append(rect)
        # pathSearch(maze, Point(0, 0), Point(self.width - 1, self.height - 1))
        self.came_from = {}
        t1 = time.perf_counter()
        self.found = breadthFirstSearch(maze, Point(0, 0), Point(self.height - 1, self.width - 1), self.came_from)
        # self.found = breadthFirstSearchQueue(maze, Point(0, 0), Point(self.width - 1, self.height - 1), self.came_from)
        # self.found = depthFirstSearch(maze, Point(0, 0), Point(self.width - 1, self.height - 1), self.came_from)
        t2 = time.perf_counter()
        print(t2 - t1)
        if self.found is not None:
            infile = open("result.txt", "a+")
            print("self.width=", self.width, ",self.height=", self.height, ",useTimes=", t2 - t1, "s", file=infile)
            infile.close()

    def draw(self, found, came_from):
        for rect in self.rectangles:
            rect.undraw()
        for rect in self.rectangles:
            rect.draw(self.win)
        if found is not None:
            pathFinishing = Stack()
            pathFinishing.push(found)
            found = came_from.get(found)
            while found is not None:
                pathFinishing.push(found)
                found = came_from.get(found)
            if not pathFinishing.is_empty():
                ps1 = pathFinishing.pop()
            while not pathFinishing.is_empty():
                ps2 = pathFinishing.pop()
                pd1 = Point(ps1.y + 1 + 0.5, self.width - ps1.x + 0.5)
                pd2 = Point(ps2.y + 1 + 0.5, self.width - ps2.x + 0.5)
                pds = Line(pd1, pd2)
                pds.setArrow("last")
                pds.setFill(color_rgb(255, 151, 98))
                pds.draw(self.win)
                ps1 = ps2
        # update(30)


def main(size):
    win = GraphWin('MazeDraw', 800, 800, autoflush=False)
    maze = Maze(size, size)
    maze.print()
    mazedraw = MazeDraw(win, maze)

    while win.checkKey() != 'Escape':
        mazedraw.draw(mazedraw.found, mazedraw.came_from)
    win.close()
    # mazedraw.draw(mazedraw.found, mazedraw.came_from)
    # win.close()


def pathSearch(array, start_point, target_point):
    """
    路径搜索
    :param array: 参数是二维数组，用来记录整个迷宫位置
    :param start_point: 起点，类型为Point
    :param target_point: 目标点，类型为Point
    :return:
    """
    came_from = {}
    found = breadthFirstSearch(array, start_point, target_point, came_from)
    # found = depthFirstSearch(array, start_point, target_point, came_from)
    if found is not None:
        pathFinishing = Stack()
        pathFinishing.push(found)
        found = came_from.get(found)
        while found is not None:
            pathFinishing.push(found)
            found = came_from.get(found)
        while not pathFinishing.is_empty():
            print(pathFinishing.pop(), end='->\n')


def breadthFirstSearch(array, start_point, target_point, came_from):
    """
    宽度优先搜索/广度优先搜索，核心代码
    :param array: 参数是二维数组，用来记录整个迷宫位置
    :param start_point: 起点，类型为Point
    :param target_point: 目标点，类型为Point
    :param came_from:
    :return:
    """
    # 未访问位置存储
    noVisited = [start_point]
    # 已访问存储节点
    hasVisited = []
    # 用来存放路径链
    came_from[start_point] = None
    while len(noVisited) != 0:
        start_point = noVisited.pop(0)
        if int(start_point.x) == int(target_point.x) and int(start_point.y) == int(target_point.y):
            return start_point
        else:
            hasVisited.append(start_point)
            # 获取邻近节点
            nearPoint = getAdjacentPointWithNoVisited(array, start_point, hasVisited)
            for point in nearPoint:
                # 未优化
                # noVisited.append(point)
                # came_from[point] = start_point

                # 未访问为空
                if len(noVisited) == 0:
                    noVisited.append(point)
                    came_from[point] = start_point
                else:
                    # 设置零为标志
                    i = 0
                    # 判断临近点是否存在未访问节点，这样就可以去除重复
                    for noVisitedPoint in noVisited:
                        if int(noVisitedPoint.x) == int(point.x) and int(noVisitedPoint.y) == int(point.y):
                            # 状态值为一说明存在，否则为零
                            i = 1
                    # 如果状态值为零，说明当前临近节点不在未访问节点中
                    if i == 0:
                        noVisited.append(point)
                        came_from[point] = start_point
    return None


def depthFirstSearch(array, start_point, target_point, came_from):
    """
    深度优先搜索
    :param array: 参数是二维数组，用来记录整个迷宫位置
    :param start_point: 起点，类型为Point
    :param target_point: 目标点，类型为Point
    :param came_from:
    :return:
    """
    noVisited = Stack()
    noVisited.push(start_point)
    came_from[start_point] = None
    # 字典
    hasVisited = {}
    while not noVisited.is_empty():
        start_point = noVisited.pop()
        if hasVisited.get(start_point) is None:
            if int(start_point.x) == int(target_point.x) and int(start_point.y) == int(target_point.y):
                return start_point
            else:
                hasVisited[start_point] = True
                ne = getAdjacentPointWithNoVisited(array, start_point, hasVisited)
                for point in ne:
                    noVisited.push(point)
                    came_from[point] = start_point
    return None


def getAdjacentPointWithNoVisited(array, point, visited):
    """
    检查相邻坐标的可执行坐标（未访问坐标）
    :param array: 二维数组
    :param point: 待检查点
    :param visited: 已经访问节点记录
    :return: 返回与此point相邻未访问节点的节点，如果该节点不存在未访问的节点返回None
    """
    filterValue = Maze.OBSTACLE
    x = array.numRows()
    y = array.numCols()
    pointX = int(point.x)
    pointY = int(point.y)
    # 检查当前节点的合法性
    if array[pointX, pointY] != 1:
        near = []
        if 0 <= pointX <= x and 0 <= pointY <= y:
            # BOTTOM 检查该节点下节点是否可行
            if pointY + 1 < y and array[pointX, pointY + 1] != filterValue:
                i = 0
                for points in visited:
                    if int(points.x) == pointX and int(points.y) == pointY + 1:
                        i = 1
                if i == 0:
                    near.append(Point(pointX, pointY + 1))
            # LEFT 检查该节点左节点是否可行
            if 0 <= pointX - 1 and array[pointX - 1, pointY] != filterValue:
                i = 0
                for points in visited:
                    if int(points.x) == pointX - 1 and int(points.y) == pointY:
                        i = 1
                if i == 0:
                    near.append(Point(pointX - 1, pointY))
            # RIGHT 检查该节点右节点是否可行
            if pointX + 1 < x and array[pointX + 1, pointY] != filterValue:
                i = 0
                for points in visited:
                    if int(points.x) == pointX + 1 and int(points.y) == pointY:
                        i = 1
                if i == 0:
                    near.append(Point(pointX + 1, pointY))
            # TOP 检查该节点的上节点是否可行
            if 0 <= pointY - 1 and array[pointX, pointY - 1] != filterValue:
                i = 0
                for points in visited:
                    # 如果该节点上节点存在定flag为1，否则代表visited中不存在该节点的上节点
                    if int(points.x) == pointX and int(points.y) == pointY - 1:
                        i = 1
                if i == 0:
                    near.append(Point(pointX, pointY - 1))
        return near
    return None


def breadthFirstSearchQueue(array, start_point, target_point, came_from):
    """
    宽度优先搜索/广度优先搜索，核心代码
    :param array: 参数是二维数组，用来记录整个迷宫位置
    :param start_point: 起点，类型为Point
    :param target_point: 目标点，类型为Point
    :param came_from:
    :return:
    """
    # 未访问位置存储

    noVisited = Queue()
    noVisited.enqueue(start_point)
    # 已访问存储节点
    hasVisited = {}
    # 用来存放路径链
    came_from[start_point] = None
    while not noVisited.is_empty():
        start_point = noVisited.dequeue()
        if int(start_point.x) == int(target_point.x) and int(start_point.y) == int(target_point.y):
            return start_point
        else:
            hasVisited[start_point] = True
            # 获取邻近节点
            ne = getAdjacentPointWithNoVisited(array, start_point, hasVisited)
            for point in ne:
                noVisited.enqueue(point)
                came_from[point] = start_point
    return None


if __name__ == '__main__':
    i = 0
    # while i < 10:
    main(20)
    # i += 1
